COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00006 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a29.tex[106,phy] \today\hfill}

\bigskip
\noindent {\bf Example.} (Dynamic Programming.)

In how many ways can we write a sequence of four positive numbers
$0≤A<B<C<D$, each larger than the one before it, that add up to~20,
like $2+4+5+9$?

If we try to generalize the problem to a sequence of $N$~numbers that
add up to~$S$, we run into difficulties. If we let $f(N,S)$ be the
number of such sequences, and try to get $f(4,20)$ as the sum of $f(3,I)$
for all possible sums of the first three variables, we count some sequences
that don't belong. Assume the last of the four variables is~9; then
$f(3,11)$ is the number of ways to pick the first three, but that number
includes $0+1+10$ and $0+2+9$, violating the rules.

We need a third argument to impose a limit of 8 on the first three
variables. Let $f(N,S,M)$ be the number of ways to pick variables
$0≤x↓1<x↓2<\cdots <x↓n≤M$ so that they add up to~$S$.
Then:

\disleft 25pt:(1):
If $N=S=0$, $f(N,S,M)=1$.

\disleft 25pt:(2):
If $N=0$, $S≠0$, $f(N,S,M)=0$.

\disleft 25pt:(3):
For $N>0$, $f(N,S,M)=$

\display 130pt:(Case where $x↓N=M$):\qquad$f(N-1,S-M,M-1)+$

\display 130pt:(Case where $x↓n<M$):\qquad$f(N,S,M-1)$

\noindent
with appropriate exceptions for $M=0$ and $S<M$. Notice that $f(3,11,8)$
is the number we needed above. Computing $f$ by dynamic programming is 
left as an exercise.

\bigskip
\noindent{\bf Exercise.} (Dynamic Programming.)

John McLendl is leading Vitas Connors by 2--0 in a tennis match, where the
match will go to the first player to reach a score of at least~7 that
is at least two points ahead of the opponent. In each individual game
(point) of the match, the experts say VC is a 6 to~7 favorite over~JM.
When the match is tied at 5--5 or more, the chance that JM will
be the first to go two points ahead and win is therefore
${6\cdot 6\over 6\cdot 6+7\cdot 7}={36\over 85}$. (Take my word for it.)
You have flunked out of school, and are working as a bookie. Martina Evert
Austin wants to place a \$10000 bet before the next serve. Write a program
to calculate the chance that JM will win.

\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft September 10, 1984

\bye